package com.kevin.Code.Hash;

import scala.Array;
import scala.Int;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author Vinlee Xiao
 * @Classname FourSum
 * @Description Leetcode 18. 四数之和 中等难度  要再做 参考官方题解
 * @Date 2021/10/25 11:27
 * @Version 1.0
 */
public class FourSum {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> combine = new ArrayList<>();

    /**
     * 回溯写法
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {

        int len = nums.length;
        if (len < 4) {
            return new ArrayList<>();
        }

        //排序
        Arrays.sort(nums);
//        for (int i : nums) {
//            System.out.print(i + " ");
//        }
        dfs(nums, target, 0, 0, 0);


        return result;
    }


    /**
     * 原始方法 超过时间限制 通过277 个样例 估计出题者 已经想到 我会用 回溯法
     *
     * @param nums
     * @param target
     */
    public void dfs(int[] nums, int target, int startIndex, int cnt, int preSum) {

        if (cnt > 4 || (cnt == 4 && preSum != target) || startIndex > nums.length) {

            return;
        }

        if (cnt == 4 && preSum == target) {

            result.add(new ArrayList<>(combine));
            return;
        }

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = startIndex; i < nums.length; i++) {

            if (hashMap.containsKey(nums[i])) {
                continue;
            }
            hashMap.put(nums[i], 1);
            combine.add(nums[i]);


            dfs(nums, target, i + 1, cnt + 1, preSum + nums[i]);

            combine.remove(combine.size() - 1);
        }

    }


    /**
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum1(int[] nums, int target) {

        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        int len = nums.length;
        if (len < 4) {
            return new ArrayList<>();
        }
//        System.out.println(target);
//        System.out.println(len);
        for (int i = 0; i < len - 3; i++) {
//            System.out.println(nums[i]);
            //为了避免产生重复的的子数据
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            //确定了第一个数如果 加上后面三个数之和大于target,则直接跳出
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {

                break;
            }

            //直接到下一个数，剪枝 产生移除了

            if ((nums[len - 3] != 1000000000 && nums[len - 2] != 1000000000) && nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
                continue;
            }
//            System.out.println(nums[i]);
            for (int j = i + 1; j < len - 2; j++) {

                //为避免产生子数组
                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }
                //如果确认了前面两个数，与后面两数之和大于target 直接跳出循环
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                //跳过
                if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {
                    continue;
                }

                //双指针
                int left = j + 1;
                int right = len - 1;
                //

                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
//                    System.out.println(sum);
                    //如果和为target
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum > target) {
                        right--;
                    } else {
                        left++;
                    }

                }


            }

        }
        return result;
    }


    public static void main(String[] args) {
        FourSum fourSum = new FourSum();
        int[] nums = new int[]{0, 0, 0, 1000000000, 1000000000, 1000000000, 1000000000};
//        int target = -1;


        List<List<Integer>> lists = fourSum.fourSum1(nums, 1000000000);

        System.out.println(lists.size());
        for (List<Integer> list : lists) {
            for (Integer e : list) {
                System.out.print(e + " ");
            }
            System.out.println();
        }
    }
}
